package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreeInorderTraversal94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (stack.size() > 0 || root != null) {
            while (root != null) {
                //根入栈
                stack.push(root);
                //循环处理左子树
                root = root.left;
            }
            //左子树处理完毕，处理根
            root = stack.pop();
            //访问根节点
            list.add(root.val);
            //处理右子树
            root = root.right;
        }
        return list;
    }


    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            inorderTraversal(root, list);
            return list;
        }

        private void inorderTraversal(TreeNode root, List<Integer> list) {
            if (root == null) return;
            //遍历左子树
            inorderTraversal(root.left, list);
            //遍历根节点
            list.add(root.val);
            //遍历右子树
            inorderTraversal(root.right, list);
        }
    }
}
